package com.test.daily.leetcode.y2022.m05.day0522.v04;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/22 下午 05:23
 * @version: 1.0
 */
public class Solution {
    public static class Node{
        int value;
        Node left;
        Node right;
        public Node(int value){
            this.value = value;
        }
    }
    public static int maxWidthUseMap(Node root){
        int ans = 0;
        if(root == null){
            return ans;
        }
        Queue<Node> queue = new LinkedList<>();
        HashMap<Node, Integer> levelMap = new HashMap<>();
        int curLevel = 1;
        int maxNodeCounts = 0;
        levelMap.put(root, 1);
        queue.add(root);
        while(!queue.isEmpty()){
            Node node = queue.poll();
            int level = levelMap.get(node);
            if(node.left != null){
                queue.add(node.left);
                levelMap.put(node.left, level + 1);
            }
            if(node.right != null){
                queue.add(node.right);
                levelMap.put(node.right, level + 1);
            }
            if(level == curLevel){
                maxNodeCounts++;
            } else{
                maxNodeCounts = 1;
                curLevel++;
                ans = Math.max(ans, maxNodeCounts);
            }
        }
        ans = Math.max(ans, maxNodeCounts);
        return ans;
    }
    public static int maxWidthWithNoMap(Node root){
        if(root == null){
            return 0;
        }
        Node nextEnd = root;
        Node curEnd = root;
        int maxNodes = 0;
        Queue<Node> queue = new LinkedList<>();
        int ans = 0;
        queue.add(root);
        while(!queue.isEmpty()){
            Node node = queue.poll();
            if(node.left != null){
                queue.add(node.left);
                nextEnd = node.left;
            }
            if(node.right != null){
                queue.add(node.right);
                nextEnd = node.right;
            }
            maxNodes++;
            if(node == curEnd){
                ans = Math.max(ans, maxNodes);
                curEnd = nextEnd;
                maxNodes = 0;
            }
        }
        ans = Math.max(ans, maxNodes);
        return ans;
    }
}
